/*
 * @lc app=leetcode.cn id=92 lang=cpp
 *
 * [92] 反转链表 II
 */

#include "include.h"

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        int reserveNum = right-left+1;
        std::vector<ListNode*> nodeVec;
        nodeVec.reserve(reserveNum);

        if (left == 1){
            for (int i=0;i<reserveNum;i++){
                nodeVec.emplace_back(head);
                head = head->next;
            }
            for (int i=reserveNum-1;i>0;i--){
                nodeVec[i]->next = nodeVec[i-1];
            }
            nodeVec[0]->next = head;
            return nodeVec[reserveNum-1];
        }else{
            ListNode* headNodexPtr = head;
            for (int i=1;i<left-1;i++){
                headNodexPtr = headNodexPtr->next;
            }
            // now headNodexPtr points to 1
            ListNode* start = headNodexPtr->next;
            for (int i=0;i<reserveNum;i++){
                nodeVec.emplace_back(start);
                start = start->next;
            }
            // now start points to 4->next = 5
            for (int i=reserveNum-1;i>0;i--){
                nodeVec[i]->next = nodeVec[i-1];
            }
            nodeVec[0]->next = start;
            headNodexPtr->next = nodeVec.back();
            return head;
        }
        // ListNode* end = start;
        // for (int i=0;i<right-left+1;i++){
        //     end = end->next;
        // }

        return head;
    }
};
// @lc code=end

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }
};
